package Demo01;

import java.util.Arrays;
import java.util.Collections;

public class Main {
}

class Solution {
    public static void main(String[] args) {
        System.out.println(longestPalindromeSubseq2("saebcfjcpbna"));
    }

    public static int longestPalindromeSubseq2(String s) {
        char[] s1 = s.toCharArray();
        char[] s2 = reverseString(s).toCharArray();
        //前s1的前i个和s3的前j个的最长公共子序列
        int n = s1.length;
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1[i-1] == s2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }
        return dp[n][n];
    }
    public static String reverseString(String s) {
        return new StringBuffer(s).reverse().toString();
    }

    public static int longestPalindromeSubseq1(String s) {
        char[] s1 = s.toCharArray();
        char[] s2 = reverseString(s).toCharArray();
        return f1(s1, s2, 0, 0);
    }

    public static int f1(char[] s1, char[] s2, int i1, int i2) {
        if (i1 == s1.length - 1 || i2 == s2.length - 1) {
            return 0;
        }
        int l;
        if (s1[i1] == s2[i2]) {
            l = f1(s1, s2, i1 + 1, i2 + 1);
        } else {
            l = Math.max(f1(s1, s2, i1, i2 + 1), f1(s1, s2, i1 + 1, i2));

        }

        return l;
    }



}